(1) Field of the Invention
The present invention relates generally to digital error correction and detection schemes. In particular, it is a design for single bit error correction and burst (multiple bit) error detection in high speed digital memories.
(2) Description of the Prior Art
Techniques and methodologies for error correction and detection have existed for over thirty years. Early attempts at error correction and detection were only capable of detecting and correcting single bit errors. More complex error correction and detection schemes capable of correcting and detecting multiple bit errors were later developed. In many of the prior art approaches to error correction and detection these two functions are performed serially. Earlier in the prior art the error correction and detection process comprises: (1) check bits are regenerated from the received information bit; (2) syndrome bits are generated by comparing the regenerated check bits and the received check bits; (3) the syndrome bits are decoded to determine the erroneous location; and (4) the error correction is accomplished by complementing the erroneous bit located by decoding the syndrome.
With the advent of modern high speed memories, these complex schemes proved to be too time intensive and a less complex parity scheme capable of correcting single bit errors and detecting double bit errors was adopted.
The prior art includes one-step majority decoding in conjunction with single and multiple error correction, and related coding and design. A discussion of this may be found in M. Y. Hsiao, D. C. Bossen and R. T. Chien, "Orthogonal Latin Square Codes", IBM J. RES. DEVELOP., pp. 390-394, July 1970, which is hereby incorporated herein by cross-reference. Moreover for purposes of single error processing, the prior art approach only accommodates a specific format arrangement of information unit (commonly referred to as "data word"). This specific format is characterized as having a data word size of "p" bits, and involving partitioning with a size of partition of m bits, where "m" is exactly the square root of p exactly the square root of p for purposes of single error processing.
Some of the salient considerations of the present invention over the previous art include more robust error detection, separation of error detection from error correction and more flexibility in the data word length.